#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/************************
 *title : connexity 
 *author : xiaozhi
 *Date : 4.3   15:33
 ***********************/

static int *id, *sz;

void UFinit(int N)
{
	int i;
	id = malloc(N * sizeof(int));
	sz = malloc(N * sizeof(int));
	for(i = 0; i < N; i++)
	{
		id[i] = i;
		sz[i] = 1;
	}
}

int find(int X)
{
	int i = X;
	while(i != id[i])
		i = id[i];
	return i;
}

int UFfind(int p, int q)
{
	return (find(p) == find(q));
}

int UFunion(int p, int q)
{
	int i = find(p), j = find(q);
	if(i == j)
		return i;
	if(sz[i] < sz[j])
	{
		id[i] = j;
		sz[j] += sz[i];
	}
	else
	{
		id[j] = i;
		sz[j] += sz[j];
	}
	return 0;
}

void main(int argc, char **argv)
{
	int p, q, N = atoi(argv[1]);
	UFinit(N);
	while(scanf("%d %d", &p, &q) == 2)
		if(!UFfind(p, q))
		{
			UFunion(p, q);
			printf("%d %d\n", p, q);
		}
}